package msb.class05;

import org.junit.Test;
import common.sort.AbstractSort;

/**
 * 归并排序
 * 递归方法实现
 * 内部有序，外部无序
 * 归并逻辑
 * 分别持有多段数据的指针，比较后归入新队列
 */
public class Code01_MergeSort extends AbstractSort {

    public void sort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    //数据L..R有序
    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);

    }

    //L..mid 与 mid+1..R进行归并
    public static void merge(int[] arr, int L, int mid, int R) {
        int leftPoint = L;
        int rightPoint = mid + 1;
        int[] tmpArr = new int[R - L + 1];
        int tmpPoint = 0;

        //左右指针越界，归并完整
        while (leftPoint <= mid || rightPoint <= R) {
            //左边指针越界，左边归并完毕，直接取右指针值
            if (leftPoint > mid) {
                tmpArr[tmpPoint++] = arr[rightPoint++];
                continue;
            }
            //右边指针越界，右边归并完毕，直接取左指针值
            if (rightPoint > R) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
                continue;
            }

            //两边都没有越界，取最小值
            if (arr[leftPoint] <= arr[rightPoint]) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
            } else {
                tmpArr[tmpPoint++] = arr[rightPoint++];
            }
        }

        for (int i = 0; i < tmpArr.length; i++) {
            arr[L + i] = tmpArr[i];
        }
    }

    @Test
    public void test() {
        Code01_MergeSort code01_mergeSort = new Code01_MergeSort();
        code01_mergeSort.check();
    }
}
